1. Technical Field
This invention relates generally to the secure regeneration of a user""s strong secret when the user supplies a corresponding weak secret, such as a user-chosen password. For example, in computer network applications, the strong secret might be an encryption key which is used to protect the user""s highly sensitive private data (such as the user""s private key used in public key cryptography). In this example, the invention relates to the secure regeneration of the encryption key (and the secure recovery of the user""s private key) when the user supplies his password. As another example, the strong secret might be used by the user to authenticate to a server, by demonstrating to the server the user""s ability to regenerate the strong secret, without that server needing to hold data that allows the weak secret to be attacked by exhaustive trials.
2. Background Art
As a result of the continuous development of new technologies, particularly in the areas of computer networks and communications, the use of large computer networks such as the Internet is becoming more widespread. This has resulted in an increase in electronic commerce and other electronic transactions conducted over these networks. It has also resulted in increased flexibility for users, as users may increasingly access these networks from any number of locations and/or devices. The increase in electronic transactions has resulted in a corresponding increased need for security for these transactions; but the increased flexibility imposes additional requirements on security since any security measures preferably would accommodate users even as they roam across the network.
In one common scenario, the user may access the computer network from many different locations and may wish to use his private key from each location. However, at each location, he may be accessing the network from a device (hereafter referred to as a xe2x80x9cclient terminalxe2x80x9d) which cannot or does not store any data for the user, other than for transitory periods. For example, an employee might access a company""s central computer network from different terminals on the company""s premises, or a consumer might access the Internet from any web browser or might access a private network from a consumer kiosk. The client terminal typically can be trusted to execute its code in a trustworthy manner, to maintain the secrecy of sensitive data (e.g., the user""s private key or a secret shared with an application server) during the period in which the user is actively using that terminal, and to securely destroy sensitive data when the user has finished using it. Thus, the user""s private data could be securely used at the client terminal if the client terminal could somehow securely obtain a copy of the private data.
In one approach, the private data is stored on some secure hardware storage or processing token, such as a smartcard. The hardware token is physically connected to the client terminal and the private data is made accessible to the client. This approach suffers from high cost and user inconvenience since dedicated hardware is required, thus making it inappropriate for many applications.
In another approach, the private data is recovered with the assistance of other devices connected to the network (hereafter referred to as xe2x80x9cserversxe2x80x9d). In one example, recovery of the private data is part of the user""s session login process. The user authenticates by presenting a user account name and a password subject to modest (but not extreme) guessablity controls. In particular, any party attempting a password guessing attack is limited to a small number of tries and, given this control, users can be permitted reasonably friendly password choices. Once the user is authenticated, the client terminal recovers the user""s private data with the assistance of the servers.
The problem of recovering private data, such as a private key, into a stateless client terminal has been addressed in prior work through the use of a server which stores secret data for the client and facilitates the recovery process. Various protocols for using such servers, with different security and performance characteristics, were surveyed in R. Perlman and C. Kaufman, xe2x80x9cSecure Password-Based Protocol for Downloading a Private Key,xe2x80x9d Proc. 1999 Network and Distributed System Security Symposium, Internet Society, January 1999. The protocols described in that work are primarily variants or derivatives of Bellovin and Merritt""s EKE protocol (e.g., see S. Bellovin and M. Merritt, xe2x80x9cEncrypted Key Exchange: Password-based protocols secure against dictionary attacks,xe2x80x9d Proc. IEEE Symposium on Research in Security and Privacy, May 1992; and S. Bellovin and M. Merritt, xe2x80x9cAugmented Encrypted Key Exchange: a password-based protocol secure against dictionary attacks and password file compromise,xe2x80x9d ATT Labs Technical Report, 1994) and Jablon""s SPEKE protocol (e.g., see D. Jablon, xe2x80x9cStrong password-only authenticated key exchange,xe2x80x9d ACM Computer Communications Review, October 1996; and D. Jablon, xe2x80x9cExtended Password Protocols Immune to Dictionary Attack,xe2x80x9d Proc. of the WETICE ""97 Enterprise Security Workshop, June 1997. Related patents include U.S. Pat. No. 5,241,599 (xe2x80x9cCryptographic protocol for secure communicationsxe2x80x9d by Bellovin and Merritt) and U.S. Pat. No. 5,440,635 (xe2x80x9cCryptographic protocol for remote authenticationxe2x80x9d by Bellovin and Merritt). Other related server-assisted secret recovery protocols have been proposed by Gong, et al. (e.g., L. Gong, T. M. A. Lomas, R. M. Needham, and J. H. Salzer, xe2x80x9cProtecting Poorly Chosen Secrets from Guessing Attacks,xe2x80x9d IEEE Journal on Selected Areas in Communications, vol.11, no.5, June 1993, pp. 648-656; L. Gong, xe2x80x9cOptimal Authentication Protocols Resistant to Password Guessing Attacks,xe2x80x9d Proc. 8th IEEE Computer Security Foundations Workshop, Ireland, Jun. 13, 1995, pp. 24-29; and L. Gong, xe2x80x9cIncreasing Availability and Security of an Authentication Service,xe2x80x9d IEEE Journal on Selected Areas in Communications, vol. 11, no. 5, June 1993, pp. 657-662); by Wu (e.g., T. Wu, xe2x80x9cThe Secure Remote Password Protocol,xe2x80x9d Proc. 1998 Network and Distributed System Security Symposium, Internet Society, January 1998, pp. 97-111), and by Halevi and Krawcyzk (e.g., S. Halevi and H. Krawczyk, xe2x80x9cPublic-key cryptography and password protocols. Public-key cryptography and password protocols,xe2x80x9d Proceedings of the Fifth ACM Conference on Computer and Communications Security, 1998).
However, all of the above methods suffer from a significant shortcoming. The server represents a major vulnerability. If a server operator, or someone who compromises a server, wishes to determine a user""s password or private data (either of which will generally enable the attacker to masquerade as the user), viable attacks are possible, despite aspects of some approaches that minimize the sensitivity of the data stored on the server. For example, in certain of the work mentioned above, the server does not store the user""s password but instead stores a value computed as a one-way function of the password. Anyone learning that value might be able to determine the password by exhaustively applying the one-way function to guessed passwords and comparing the result with the stored value. In general terms, the previously mentioned approaches suffer from the weakness that anyone who can access the server database or can disable any throttling or lockout mechanism on the server can try passwords exhaustively until a user""s account on the server is penetrated.
In some application scenarios the above weakness can significantly undermine the attractiveness of the server-assisted approach to recovery of private data. For example, the above attack scenario significantly hampers the non-repudiation properties otherwise inherent in digital signature technology. If a roaming user digitally signs a transaction using the user""s private key from a client terminal and later wishes to deny the user""s digital signature, the user can plausibly claim that the server operator or someone who compromised the server obtained the user""s private key as described above and digitally signed the transaction posing as the user. Risks and liability faced by a server operator are reduced if it can justifiably counter claims from users that it, or its personnel, may have masqueraded as the user.
Thus there is a need for an approach that permits a client terminal to recover a user""s private data with the assistance of servers while remaining resistant to attacks on the servers. More generally, the problem of recovering private data into a stateless client can be reduced to the problem of generating and regenerating strong secret data for a user from the user""s weak secret data, such as a password. The strong secret can be used as an encryption key in a symmetric cryptosystem to encrypt and recover any amount of private data that might be held in an encrypted form in a widely accessible storage place.
There is also a need for approaches which permit a user to authenticate to an application server from a stateless client terminal on the basis of a presented password. Current approaches, such as the Kerberos authentication method (e.g., see J. T. Kohl and B. C. Neuman, The Kerberos Network Authentication Service (V5), Request for Comments (RFC) 1510, Internet Activities Board, 1993), involve the user authenticating first to an authentication server and subsequently to an application server using a cryptographic xe2x80x9cticketxe2x80x9d from the authentication server. However, these approaches suffer from the shortcoming that either the application server or an authentication server holds data which, if exposed to an attacker (either internal or external to the organization that operates the server), allows the attacker to exhaustively guess passwords and likely determine the user""s password. These problems may be averted if the user authentication is based on a user presenting evidence of knowledge of strong secret data rather than weak secret data to the application server or authentication server.
There is also a need for approaches which allow a user to create a digital signature from a stateless client terminal into which a password is entered. One approach to satisfying this requirement is to recover the user""s private key into the terminal as outlined above and to compute the digital signature in the client terminal. Another approach for satisfying the requirement, which does not require the private key to be assembled in one place, involves communications with multiple servers each of which holds an independent part of the user""s signing private key. Such servers each generate part of the digital signature and the parts are combined in the client terminal to give the full digital signature. While relevant other work on such methods achieves the goal of not assembling the private key in one place, such work suffers from the weakness that one or more servers that participate in the signing process hold data that allows the user""s password to be exhaustively attacked. Consequently, there is a risk that anyone who compromises any one such server can determine the user""s password by exhaustive guessing, which, if successful, allows the attacker to forge digital signatures purporting to be from that user. The problem can be averted by authenticating to the servers that generate parts of the digital signature by demonstrating knowledge of a strong user secret, which may have been regenerated on the basis of presentation of a weak user secret, rather than by authenticating directly on the basis of the weak user secret itself.
Thus, there is a need for an approach that permits a client terminal to regenerate a user""s strong secret data from weak secret data with the assistance of servers while remaining resistant to attacks on the servers.
In accordance with the present invention, a method for establishing (300,500) a user""s (100) strong secret data to allow subsequent recovery (400,600) of the strong secret data, includes the following steps. Weak secret data, for example a password, is determined (320) for the user (110). The user authenticates (310) to servers (130), which include secret holding servers (preferably at least two secret holding servers). Each secret holding server has corresponding server secret data. A generating client (120), possibly assisted by the secret holding servers (130), computes (330,530) the user""s strong secret data. The strong secret data is a function of the user""s weak secret data and of the server secret data. In a preferred embodiment, secret components are computed (534) for each secret holding server. Each secret component is a function of the weak secret data and of the strong secret data for that secret holding server. The secret components are combined (536) to generate the strong secret data. The generating client (120) also determines (350) verifier data for verification servers (130), preferably at least two. The verifier data enables a verification server (130) to verify (402,602) whether a device (220) has subsequently successfully recovered (400,600) the strong secret data. However, it is computationally infeasible for the server (130) to determine the weak secret data based only on access to its verifier data. The verification servers (130) may store (355) the verifier data for subsequent use. The generating client (120) may additionally use the strong secret data as a cryptographic key in a symmetric cryptosystem to encrypt (370) other private data for the user (110), such a the user""s private key.
In a preferred embodiment, the strong secret data is computed (330,530) as follows. The generating client (120) computes server request data for at least one of the secret holding servers (130). The server request data is a function of the weak secret data and of an ephemeral client secret, but the server request data does not reveal information about the weak secret data without knowledge of the ephemeral client secret. As a result, the generating client (120) can transmit the server request data to the secret holding server (130) without compromising the weak secret data. The secret holding server (130) computes server response data, which is a function of the server secret data for the secret holding server and of the received server request data. The server response data does not reveal information about the server secret data without knowledge of the weak secret data and the ephemeral client secret. As a result, the secret holding server (130) can transmit the server response data to the generating client (120) without compromising its server secret data. The generating client (120) computes a secret component for the secret holding server as a function of the server response data received from the secret holding server and of the ephemeral client secret. The secret component is a function of the weak secret data and of the server secret data but is independent of the ephemeral client secret. The generating client (120) then computes the user""s strong secret data as a function of the secret components.
In a further refinement, the weak secret data is a password PWD and the server secret data are random integers b(i), where i is an index for the servers (130). The generating client (120) computes (534) server request data which includes the value M=wa. Here, w=f(weak secret data), where f is a function which generates an element of a group G, and the ephemeral client secret includes the random integer a for which there exists a corresponding integer axe2x80x2 such that xaaxe2x80x2=x for all x in the group G. The group G is a finite group in which exponentiation is efficient but the discrete logarithm problem is computationally infeasible, for example the multiplicative group of the set of integers modulo a prime p or a group of points on an elliptic curve over a finite field. All exponentiations are calculated in the group G. The secret holding server (130) computes (534) server response data which includes the value c(i)=Mb(i). The generating client (120) then computes (534) secret components according to K(i)=h(c(i)axe2x80x2) wherein h is a function. The user""s strong secret data is then computed (536) as a function of all the secret components K(i), for example as the exclusive-OR of these components.
In another aspect of the invention, the strong secret data is recovered (400,600) from the weak secret data as follows. A recovery client (220) receives (410) the user""s weak secret data. The recovery client (220) then computes (440,640) the user""s strong secret data, which is a function of the user""s weak secret data and of server secret data for at least two secret holding servers (130). In a preferred embodiment, the computation is based on secret components, as described above. The recovery client (220) also determines (450,650) proof data for proving (460,660) that the strong secret data was successfully computed (401,601) and transmits (455,655) the proof data to verification servers (130), which may or may not also be secret holding servers. By validating the proof data using the corresponding verifier data, the verification servers (130) may determine (460,660) whether the strong secret data was successfully recovered (401,601) and take appropriate actions (680). For example, if it seems likely that an entity (220) which does not have access to the weak secret data is attempting to regenerate (401,601) the strong secret data, then the verification server might instruct the secret holding servers (130) to stop participating in any further recovery attempts (400,600). Alternately, the verification server might be responsible for generating part of a digital signature on behalf of user (110). In this case, the proof data might be accompanied by a message digest of a message to be signed and the verification server (130) will generate its part of the digital signature only when simultaneously presented with adequate proof data. If additional private data was encrypted (370) using the strong secret data as a cryptographic key, then the recovery client (220) may additionally decrypt (470) the private data.
In a preferred embodiment, the strong secret data is computed (440,640) as follows. The recovery client (220) computes (420,620) server request data for at least one and preferably more than one secret holding server. The server request data is a function of the weak secret data and of an ephemeral client secret, but it does not reveal significant information about the weak secret data without knowledge of the ephemeral client secret. The server request data is transmitted (425,625) to the secret holding server, which calculates (430,630) server response data based on the server request data and its server secret data. The server response data does not reveal significant information about the server secret data without knowledge of the server request data. The server response data is transmitted (435,635) to the recovery client (220), which recovers (440,640) the user""s strong secret data using the server response data.
In a preferred embodiment corresponding to the one described above, the recovery client (220) randomly generates (624) an ephemeral client secret a, which is an integer for which there exists a corresponding integer axe2x80x2 such that xaaxe2x80x2=x for all x in group G. It computes (626) server request data including the value M=wa where w=J(PWD) as above and transmits (625) this data to at least one secret holding server (130). Each secret holding server (130) computes (630) server response data including the value c(i)=Mb(i) and transmits (635) this back to the recovery client (220). The recovery client (220) computes (644) the secret components K(i)=h(c(i)axe2x80x2) where h is the same function as above. The secret components are then combined (646), as in the generating client (120), to recover the strong secret data.
These methods (300,400,500,600) are advantageous because they allow a user (110) to recover (400,600) strong secret data from weak secret data at many recovery clients (220). The methods are generally resistant to attacks, including attacks on or compromise of the servers (130). In further accordance with the invention, software and/or hardware (100,200) implements the above methods.